package zifuchuan;

/**
 * 获取两个字符串的最大相同子串
 * abcwerthelloyuiodef
 * cvhellobnm
 * 使用左右指针，用长度较短的字符串依次截短（每次截短可能截前面也可能截后面）与较长的字符串做比较
 */
public class _015最大相同子串 {
    public static void main(String[] args) {
        String str1 = "abcwerthelloyuiodef";
        String str2 = "cvhellobnm";
        String maxSubString = getMaxSubString(str1, str2);
        System.out.println(maxSubString);
    }

    //前提：只有一个最大相同子串
    public static String getMaxSubString(String str1,String str2){
        String maxString = (str1.length() >= str2.length()) ? str1 : str2;
        String minString = (str1.length() < str2.length()) ? str1 : str2;
        //比较次数取决于长度较短字符串的长度
        int count = minString.length();
        for (int i = 0 ; i < count ; i++){//循环比较的次数
            for (int x = 0,y = count - i ; y <= count; x++,y++){//双指针，每次截短可能截前也可能截后.某一次比较结束的条件是后面指针到达数组末尾
                String subStr = minString.substring(x,y);
                if (maxString.contains(subStr)){
                    return subStr;
                }
            }
        }
        return null;
    }
}
